class Solution {
    /**
        思路1：判断下标：val<<1 和 (val<<1)+1
        思路2：null是最后一个访问的（遍历时即使left,right为null也要加入到队列）
    
     */
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return false;
        }
        int index = 0;
        Queue<TreeNode> q = new LinkedList<>();
        root.val = 1;
        q.add(root);
        while (q.size() > 0) {
            TreeNode tot = q.poll();
            index++;
            if (index != tot.val) {
                return false;
            }
            if (tot.left != null) {
                tot.left.val = tot.val << 1;
                q.add(tot.left);
            }
            if (tot.right != null) {
                tot.right.val = (tot.val << 1) + 1;
                q.add(tot.right);
            }
        }
        return true;
    }
}